1. Field of the Invention
The present invention generally relates to techniques for compressing graphic and video data, and in more particular concerns lossy methods for compressing graphics and video.
2. Background Information
Image and video data compression refers to a process in which the amount of data used to represent images and video is reduced while the quality of the reconstructed image or video satisfies a requirement for a certain application and the complexity of computation involved is affordable for the application. Various compression schemes have been developed over the years, including both lossy and lossless schemes. As their respective names imply, in a lossy compression scheme some aspect of the original data is discarded (lost), because it was deemed unnecessary to the final application, while in a lossless scheme the original data is reproduced when the compressed image or video is decompressed.
Image and video data, like other computer data, is encoded as a series of bits. A typical still color image comprises a plurality of pixels laid out in a grid called a bitmap having multiple bitplanes laid on top of one another, wherein the number of bitplanes corresponds to the potential color resolution of the image when it is displayed on an output device such as a printer or monitor. For example, an 8-bit(plane) bitmap has a limit of 256 different colors, while a 16-bit(plane) bitmap has a limit of 65536 different colors. In addition to color images, there are black and white images (also known as monochrome, comprising one bit plane), and grayscale bitmaps (typically comprising four or eight bit planes).
In an original bitmap, data corresponding to each pixel of data must occupy a memory space equal to the number of bitplanes in the bitmap. Accordingly, a 1024×1024 pixel 24-bit bitmap requires three Mbytes of memory if it was to be stored in its original format. This is clearly excessive, and provided the original motivation for developing compression schemes to reduce the amount of memory required to store images.
When a wider range of colors is needed, it requires mixing a limited number of primary colors. There are two fundamental color mixing schemes, RGB and CMYK, depending upon the intended output medium. RGB color stand for the red, green, and blue additive primary colors typically used in devices that emit light, such a computer monitors. CMYK color stands for the cyan, magenta, and yellow subtractive primary colors, plus black for contrast, typically used for printed materials. A larger value for a given primary results in larger spots of that color, applied in a fine-pattern on a white page. Each of the three primary inks absorbs certain colors from the white light impinging on the printed page. Because CMYK operates by removing specific colors from white, it is called subtractive color.
An increasingly popular color specification method called HIS can be used independently of the mixing scheme. HIS stand for Hue, Saturation, and Intensity. Hue is what a person thinks of as the color of an object, such as orange, green or purple. Saturation describes the amount of white. The brown color of baking chocolate, for example, is very saturated, while the color of milk chocolate is the same hue, but less saturated. Intensity describes the brightness and, for example, is mainly what distinguishes an orange in sunlight form an orange in shade. Also, the word luminosity is often substituted for intensity in which case HSI becomes HSL.
Initially, image data was compressed using schemes originally designed for compressing text data—that is schemes that only considered the binary content and not the qualitative content of the data. These schemes include run-length compression, wherein a series of repeated values (i.e., identical adjacent pixels) are replaced by a single value and a count, Huffman encoding, which uses shorter codes for frequently occurring things and longer codes for infrequently occurring things, LZW (Lempel, Ziv and Welch) compression, an adaptive version of Huffman encoding, and arithmetic compression. These schemes are all candidates for lossless or near lossless compression. However, they are limited in how much compression they can produce, and are therefore not suitable for many compression requirements. An example of a popular compression scheme that uses a variable-length LZW compression algorithm is the GIF (Graphics Interchange Format), which is presently limited to 256 24-bit colors, has no provisions for storing grayscale or color-correction data, and doesn't support the CMYK or HIS models.
The most commonly cited lossy compression scheme is the baseline algorithm of JPEG (the Joint Photographic Experts Group of the International Standards Organization (ISO). Although JPEG defines several algorithms, the most commonly referred to as JPEG is the lossy, baseline algorithm. JPEG algorithms begin by separating the chroma (color) information from the luminance (brightness) information, to take advantage of the human eye's tolerance for lower color resolution. Next, the image is broken up into smaller rectangular tiles comprise 8×8 groups of pixels. The lossy algorithm then applies a mathematical technique to the tiles, known as Discrete Cosine Transform (DCT). After this transformation, individual pixels no longer exist. Rather, they are represented by a series of patterns describing how rapidly the pixels vary. Since individual pixel identities are lost in DCT, this form of JPEG is called lossy.
A primary disadvantage with JPEG is that there may be discontinuities at the boundaries of each tile. For example, while JPEG does a fairly good job of providing continuity (i.e., no rapid changes) in adjacent pixels within each tile, there is no provision for blending the pixels of the outlines of the tiles. As a result, some JPEG images, especially those that apply a high compression ratio, look like a set of tiles that are reassembled together to form a composite image. Ideally, a viewer should not perceive that individual tiles are used. This problem is especially pronounced when scaling images. Accordingly, it is desired to provide an image and video compression scheme that provides similar benefits to JPEG compression, but eliminated the discontinuities that are often caused by the compression scheme.